package com.yubest;

/**
 * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
 *
 * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
 *
 *
 *
 * 示例 1：[图片] img/0572_1.jpg
 *
 *
 * 输入：root = [3,4,5,1,2], subRoot = [4,1,2]
 * 输出：true
 * 示例 2：[图片] img/0572_2.jpg
 *
 *
 * 输入：root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
 * 输出：false
 *
 *
 * 提示：
 *
 * root 树上的节点数量范围是 [1, 2000]
 * subRoot 树上的节点数量范围是 [1, 1000]
 * -10^4 <= root.val <= 10^4
 * -10^4 <= subRoot.val <= 10^4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subtree-of-another-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/10 18:06
 */
public class P0572 {

    public static void main(String[] args) {
        System.out.println(new Solution572().isSubtree(new TreeNode(3, new TreeNode(4, new TreeNode(1), null), new TreeNode(5, new TreeNode(2), null)),
                new TreeNode(3, new TreeNode(1), new TreeNode(2))));
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution572 {

    private TreeNode suRoot;

    /**
     * 思路：先遍历root，获取到每个节点，然后一一与subRoot比对
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (null == this.suRoot) {
            this.suRoot = subRoot;
        }
        return dfs(root);
    }

    private boolean dfs(TreeNode root) {
        if (null == root) {
            return false;
        }
        return isSub(root, this.suRoot) || dfs(root.left) || dfs(root.right);
    }

    private boolean isSub(TreeNode root, TreeNode subRoot) {
        if (null == root && null == subRoot) {
            return true;
        }
        if (null == root || null == subRoot || root.val != subRoot.val) {
            return false;
        }
        return isSub(root.left, subRoot.left) && isSub(root.right, subRoot.right);
    }
}
